package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Marioszk
 * leetcode 102: 给你一个二叉树，请你返回其按层序遍历得到的节点值。 （即逐层地，从左到右访问所有节点）。
 * 示例，给定二叉树：[3,9,20,null,null,15,7]
 */
public class TreeNodeValue_层序遍历得到的节点值 {

    private static class Node {
        /**
         * 节点值
         */
        public int value;
        /**
         * 左节点
         */
        public Node left;
        /**
         * 右节点
         */
        public Node right;

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public static List<List<Integer>> bfsWithBinaryTreeLevelOrderTraversal(Node root) {
        if (root == null) {
            return Arrays.asList();
        }

        List<List<Integer>> result = new ArrayList<>();

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Integer> values = new ArrayList<>();
            int levelNum = queue.size();
            // 依次遍历每一层节点
            for (int i = 0; i < levelNum; i++) {
                Node node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                values.add(node.value);
            }
            // 遍历完当前层，添加值到结果中
            result.add(values);
        }
        return result;
    }

    private static final List<List<Integer>> traversalList = new ArrayList<>();

    /**
     * 使用深度优先遍历计算层的值
     *
     * @param root
     * @param level
     */
    public static void dfs(Node root, int level) {
        if (root == null) {
            return;
        }
        // 判断每一层是否已经有值集合,没有添加
        if (traversalList.size() < level + 1) {
            traversalList.add(new ArrayList<>());
        }

        // 取出当前层的值集合
        List<Integer> levelList = traversalList.get(level);
        levelList.add(root.value);
        // 遍历左节点
        dfs(root.left, level + 1);
        // 遍历右节点
        dfs(root.right, level + 1);
    }
}
